#define _CRT_SECURE_NO_WARNINGS 1
bool cmp(vector<int>& a, vector<int>& b) {
    if (a[0] == b[0])return a[1] > b[1];
    return a[0] < b[0];
}

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if (envelopes.empty()) {
            return 0;
        }
        int len = envelopes.size();
        vector<int> ans;
        sort(envelopes.begin(), envelopes.end(), cmp);
        ans.push_back(envelopes[0][1]);

        for (int i = 1; i < len; i++) {
            // cout<<envelopes[i][0]<<" "<<envelopes[i][1]<<endl;
            if (envelopes[i][1] > ans[ans.size() - 1]) {
                ans.push_back(envelopes[i][1]);
            }
            else {
                int l = -1;
                int r = ans.size();
                while (l + 1 != r) {
                    int mid = (l + r) >> 1;
                    if (ans[mid] < envelopes[i][1]) {
                        l = mid;
                    }
                    else {
                        r = mid;
                    }
                }
                if (r >= 0 && r < ans.size()) {
                    ans[r] = envelopes[i][1];
                }
                // cout<<l<<" ---"<<endl;
            }

            //   for(auto it:ans)cout<<it<<" ";
            //   cout<<endl;
        }
        return ans.size();
    }
};
